/*  tBookShelf: Hyphenation class
    (C) 2007  TvN (Volodymyr Tarasenko), e-mail: tvntsr@yahoo.com

    Based on LibHnj - a library for high quality hyphenation and justification
    Copyright (C) 1998 Raph Levien
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "Utils/Hyphenation.hpp"

using namespace std;

namespace __gnu_cxx
{
    template<> struct hash< std::string >
    {
        size_t operator()( const std::string& x ) const
        {
            int len = x.size();
            unsigned int h=0, g;
        
            for(int i = 0; i < len; ++i) 
            {
                h = ( h << 4 ) + x[i];
                if ( ( g = h & 0xf0000000 ) ) {
                    h = h ^ (g >> 24);
                    h = h ^ g;
                }
            }
            return h; /* % M */
        }
    };
}

/* Get the state number, allocating a new state if necessary. */
int
HyphenDict::get_state (HashTab& hashtab, const std::string& str)
{
    HashTab::const_iterator p = hashtab.find(str);
    if (p != hashtab.end())
    {
        return p->second;
    }

    int used = dict.size();

    HashTab::value_type item(str, used);
    hashtab.insert(item);
    
    if (!(used & (used - 1)))
    {
        dict.reserve(used << 1);
    }

    dict.push_back(HyphenState());

    return used++; 
}


/* add a transition from state1 to state2 through ch - assumes that the
   transition does not already exist */
void
HyphenDict::add_trans(const int& state1, const int& state2, const char& ch)
{
    HyphenState::trans_type &trans = dict[state1].trans;
    
    int num_trans = trans->size();
    if (!(num_trans & (num_trans - 1)))
    {
        trans->reserve(num_trans << 1);
    }

    trans->push_back( HyphenTrans(ch, state2) );
}

static std::string Empty;

void HyphenDict::read_dict(std::istream& f)
{
    HashTab hash_tab;

    HashTab::value_type def(Empty, 0);
    hash_tab.insert(def);

    //dict.push_back(dict_elem(new HyphenState()));
    dict.push_back(HyphenState());

    std::string buf;

    getline(f, cset);

    std::string pattern;
    std::string word;

    while (f.good())
    {
        getline(f, buf);
        if ((buf.empty()) ||
            (buf[0] == '%'))
        {
            continue;
        }

        int j = 0;
        
        word.clear();
        pattern.assign(buf.size(), '0');

        for (int i = 0; buf[i] > ' '; i++)
        {
            if (isdigit(buf[i]))
            {
                pattern[j] = buf[i];
            }
            else
            {    
                word += buf[i];
                ++j;
            }
        }
//        word.erase(j, std::string::npos);
        pattern.erase(j + 1, std::string::npos);

        /* Optimize away leading zeroes */
        int lead_zeroes = pattern.find_first_not_of('0');

        HashTab::iterator found = hash_tab.find(word);

        int state_num = get_state (hash_tab, word);

        //if (lead_zeroes != string::npos)
        dict[state_num].match = pattern.substr(lead_zeroes, string::npos);

        /* now, put in the prefix transitions */
        for (; found == hash_tab.end(); j--)
        {
            int last_state = state_num;
            char ch = word[j - 1];
            word.erase(j-1, string::npos);

            found = hash_tab.find(word);

            state_num = get_state (hash_tab, word);
            add_trans (state_num, last_state, ch);
        }
    }

    /* put in the fallback states */
    int state_num = 0;
    for (HashTab::iterator p = hash_tab.begin();
         p != hash_tab.end();
         ++p)
    {
        for (int j = 1; 1; j++)
        {
            state_num = hash_tab[p->first.size()>j ? p->first.substr(j): ""];
            if (state_num >= 0)
                break;
        }
        dict[p->second].fallback_state = state_num;
    }
}

void HyphenDict::hyphenate(const std::string& word,
                           std::string& hyphens)
{
    int j = 0;

    string prep_word(".");

    for (int i = 0; i < word.size(); i++)
        if (isalpha (word[i]))
        {
            j++;
            prep_word += tolower (word[i]);
        }
    j++;
    prep_word += '.';

    hyphens.assign(j, '0');

    /* now, run the finite state machine */
    int state = 0;

    for (int i = 0; i < j; i++)
    {
        char ch = prep_word[i];
        for (;;)
	{
            HyphenState& hstate = dict[state];
            int cnt = hstate.trans->size();
            for (int k = 0; k < cnt; k++)
                if ((*hstate.trans)[k].ch == ch)
                {
                    state = (*hstate.trans)[k].new_state;
                    goto found_state;
                }
            state = hstate.fallback_state;
	}
    found_state:
        /* Additional optimization is possible here - especially,
           elimination of trailing zeroes from the match. Leading zeroes
           have already been optimized. */
        std::string& match = dict[state].match;
        if (!match.empty())
	{
            int offset = i + 1 - match.size();
            /* This is a linear search because I tried a binary search and
               found it to be just a teeny bit slower. */
            for (int k = 0; k < match.size(); k++)
                if (hyphens[offset + k] < match[k])
                    hyphens[offset + k] = match[k];
	}
    }

    hyphens.replace(0, 2, 1, '0');

    int cnt = word.size() - (j -4);
    hyphens.replace(j-4, cnt, cnt, '0');
}


/// Test
#ifdef TEST_CASE

#include <iostream>

int main(int argc, char** argv)
{
    if (argc != 3)
    {
        cerr << "correct syntax is:\n"
             << "example hyphen_dictionary_file word_to_check\n"
             << endl;
        exit(1);
    }

    string df(argv[1]);
    string wtc(argv[2]);

    try{
        HyphenDict dict(df);

        int n = wtc.size()-1;
        while((n >=0) && (wtc[n] == '.')) n--;
        n++;

        wtc.erase(n);

        std::string hyphens;
        cerr << "word to hyphenate ["
             << wtc
             << "]"
             << endl;

        dict.hyphenate(wtc, hyphens);

        cerr << "res:" << hyphens << endl;

        string hyphword;
        for (int i = 0; i < n; i++) {
            hyphword += wtc[i];
            if (hyphens[i]&1)
            {
                hyphword += '-';
            }
        }

        cerr << "Final:" << hyphword << endl;

    }catch(std::exception& exc)
    {
        cerr << exc.what()
             << endl;
    }

}
#endif //TEST_CASE
